package 动态规划.背包And分组And切割问题系列;

import org.junit.Test;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/7/24 10:24
 */
public class lc2787将一个数字表示成幂和的方案 {
    /*
     这个思维转化 很妙
     */
    static final int MOD = 1000000007;
    public int solve(int n,int x){

        /*
         r 适当的 大一些 无所谓的， 这一点要明白！
         */
        double temp = 1.0 / x;
        int r = (int)Math.pow(n,temp) + 3;
        int dp[][] = new int[r + 1][n + 1];
        dp[r - 1][0] = 1;
        for(int index = r - 1;index >= 1;index--){
            dp[index][0] = 1;
            for(int rest = 1;rest <= n;rest++){
                // choose
                dp[index][rest] = dp[index + 1][rest] % MOD ;
                if(rest - (int)Math.pow(index,x) >= 0){
                    dp[index][rest] = ((dp[index + 1][rest - (int)Math.pow(index,x)] % MOD) + dp[index][rest]) % MOD;
                }
            }
        }
        return dp[1][n];
    }


    public static void main(String[] args) {
        int n = 64;
        double temp = 1.0 / 3;
        System.out.println(temp);
        double ans = Math.pow(n,temp);
        System.out.println(ans);
        System.out.println((int)ans);
    }
    @Test
    public void test(){
        System.out.println(solve(10,2));
        System.out.println(solve(4,1));
        System.out.println(solution(64,3));
    }

    public int recursion(int index,int rest,int r,int x,Integer dp[][]){
        if(rest == 0){
            return 1;
        }
        if(index == r){
            return 0;
        }
        if(dp[index][rest] != null){
            return dp[index][rest];
        }
        int ans = 0;
        ans = recursion(index + 1,rest,r,x,dp) % MOD;

        if(rest - (int) Math.pow(index,x) >= 0){
            ans =(ans + recursion(index + 1,rest - (int)Math.pow(index,x),r,x,dp)) % MOD;
        }
        return dp[index][rest] = ans;
    }



    public int solution(int n,int x){
        int i ;
        for( i  = 1;i <= n;i++){
            int temp  = (int)Math.pow(i,x);
            if(temp > n){
                break;
            }
        }
        Integer dp[][] = new Integer[i][n + 1];
        recursion(1,n,i,x,dp);
        return dp[1][n];
    }



/*
 arignote  是真的 牛逼
 */
    class Solution {

        public int numberOfWays(int n, int x) {
            int[] dp = new int[n + 1];
            dp[0] = 1;
            for (int i = 1; i <= n; i++) {
                for (int j = n; j >= Math.pow(i, x); j--) {
                    dp[j] = (dp[j] + dp[j - (int) Math.pow(i, x)]) % 1000000007;
                }
            }
            return dp[n];
        }
    }


}
